home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 1999 August / SGI Freeware 1999 August.iso / dist / samba.idb / usr / samba / src / source / ubiqx / ubi_Cache.c.z / ubi_Cache.c
Encoding:
C/C++ Source or Header  |  1998-10-28  |  20.2 KB  |  491 lines
  1. /* ========================================================================== **
  2.  *                                 ubi_Cache.c
  3.  *
  4.  *  Copyright (C) 1997 by Christopher R. Hertel
  5.  *
  6.  *  Email: crh@ubiqx.mn.org
  7.  * -------------------------------------------------------------------------- **
  8.  *
  9.  *  This module implements a generic cache.
  10.  *
  11.  * -------------------------------------------------------------------------- **
  12.  *
  13.  *  This library is free software; you can redistribute it and/or
  14.  *  modify it under the terms of the GNU Library General Public
  15.  *  License as published by the Free Software Foundation; either
  16.  *  version 2 of the License, or (at your option) any later version.
  17.  *
  18.  *  This library is distributed in the hope that it will be useful,
  19.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  20.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21.  *  Library General Public License for more details.
  22.  *
  23.  *  You should have received a copy of the GNU Library General Public
  24.  *  License along with this library; if not, write to the Free
  25.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  26.  *
  27.  * -------------------------------------------------------------------------- **
  28.  *
  29.  *  This module uses a splay tree to implement a simple cache.  The cache
  30.  *  module adds a thin layer of functionality to the splay tree.  In
  31.  *  particular:
  32.  *
  33.  *    - The tree (cache) may be limited in size by the number of
  34.  *      entries permitted or the amount of memory used.  When either
  35.  *      limit is exceeded cache entries are removed until the cache
  36.  *      conforms.
  37.  *    - Some statistical information is kept so that an approximate
  38.  *      "hit ratio" can be calculated.
  39.  *    - There are several functions available that provide access to
  40.  *      and management of cache size limits, hit ratio, and tree
  41.  *      trimming.
  42.  *
  43.  *  The splay tree is used because recently accessed items tend toward the
  44.  *  top of the tree and less recently accessed items tend toward the bottom.
  45.  *  This makes it easy to purge less recently used items should the cache
  46.  *  exceed its limits.
  47.  *
  48.  *  To use this module, you will need to supply a comparison function of
  49.  *  type ubi_trCompFunc and a node-freeing function of type
  50.  *  ubi_trKillNodeTrn.  See ubi_BinTree.h for more information on
  51.  *  these.  (This is all basic ubiqx tree management stuff.)
  52.  *
  53.  *  Notes:
  54.  *
  55.  *  - Cache performance will start to suffer dramatically if the
  56.  *    cache becomes large enough to force the OS to start swapping
  57.  *    memory to disk.  This is because the nodes of the underlying tree
  58.  *    will be scattered across memory in an order that is completely
  59.  *    unrelated to their traversal order.  As more and more of the
  60.  *    cache is placed into swap space, more and more swaps will be
  61.  *    required for a simple traversal (...and then there's the splay
  62.  *    operation).
  63.  *
  64.  *    In one simple test under Linux, the load and dump of a cache of
  65.  *    400,000 entries took only 1min, 40sec of real time.  The same
  66.  *    test with 450,000 records took 2 *hours* and eight minutes.
  67.  *
  68.  *  - In an effort to save memory, I considered using an unsigned
  69.  *    short to save the per-entry entry size.  I would have tucked this
  70.  *    value into some unused space in the tree node structure.  On
  71.  *    32-bit word aligned systems this would have saved an additional
  72.  *    four bytes per entry.  I may revisit this issue, but for now I've
  73.  *    decided against it.
  74.  *
  75.  *    Using an unsigned short would limit the size of an entry to 64K
  76.  *    bytes.  That's probably more than enough for most applications.
  77.  *    The key word in that last sentence, however, is "probably".  I
  78.  *    really dislike imposing such limits on things.
  79.  *
  80.  *  - Each entry keeps track of the amount of memory it used and the
  81.  *    cache header keeps the total.  This information is provided via
  82.  *    the EntrySize parameter in ubi_cachePut(), so it is up to you to
  83.  *    make sure that the numbers are accurate.  (The numbers don't even
  84.  *    have to represent bytes used.)
  85.  *
  86.  *    As you consider this, note that the strdup() function--as an
  87.  *    example--will call malloc().  The latter generally allocates a
  88.  *    multiple of the system word size, which may be more than the
  89.  *    number of bytes needed to store the string.
  90.  *
  91.  * -------------------------------------------------------------------------- **
  92.  *
  93.  *  Log: ubi_Cache.c,v
  94.  *  Revision 0.0  1997/12/18 06:24:33  crh
  95.  *  Initial Revision.
  96.  *
  97.  * ========================================================================== **
  98.  */
  99.  
  100. #include <stdlib.h>     /* Defines NULL. */
  101. #include "ubi_Cache.h"  /* Header for *this* module. */
  102.  
  103. /* -------------------------------------------------------------------------- **
  104.  * Static data...
  105.  */
  106.  
  107. static char ModuleID[] = 
  108. "ubi_Cache\n\
  109. \tRevision: 0.0\n\
  110. \tDate: 1997/12/18 06:24:33 GMT\n\
  111. \tAuthor: crh\n";
  112.  
  113. /* -------------------------------------------------------------------------- **
  114.  * Internal functions...
  115.  */
  116.  
  117. static void free_entry( ubi_cacheRootPtr CachePtr, ubi_cacheEntryPtr EntryPtr )
  118.   /* ------------------------------------------------------------------------ **
  119.    * Free a ubi_cacheEntry, and adjust the mem_used counter accordingly.
  120.    *
  121.    *  Input:  CachePtr  - A pointer to the cache from which the entry has
  122.    *                      been removed.
  123.    *          EntryPtr  - A pointer to the already removed entry.
  124.    *
  125.    *  Output: none.
  126.    *
  127.    *  Notes:  The entry must be removed from the cache *before* this function
  128.    *          is called!!!!
  129.    * ------------------------------------------------------------------------ **
  130.    */
  131.   {
  132.   CachePtr->mem_used -= EntryPtr->entry_size;
  133.   (*CachePtr->free_func)( (void *)EntryPtr );
  134.   } /* free_entry */
  135.  
  136. static void cachetrim( ubi_cacheRootPtr crptr )
  137.   /* ------------------------------------------------------------------------ **
  138.    * Remove entries from the cache until the number of entries and the amount
  139.    * of memory used are *both* below or at the maximum.
  140.    *
  141.    *  Input:  crptr - pointer to the cache to be trimmed.
  142.    *
  143.    *  Output: None.
  144.    *
  145.    * ------------------------------------------------------------------------ **
  146.    */
  147.   {
  148.   while( ( crptr->max_entries && (crptr->max_entries < crptr->root.count) )
  149.       || ( crptr->max_memory  && (crptr->max_memory  < crptr->mem_used)   ) )
  150.     {
  151.     if( !ubi_cacheReduce( crptr, 1 ) )
  152.       return;
  153.     }
  154.   } /* cachetrim */
  155.  
  156.  
  157. /* -------------------------------------------------------------------------- **
  158.  * Exported functions...
  159.  */
  160.  
  161. ubi_cacheRootPtr ubi_cacheInit( ubi_cacheRootPtr  CachePtr,
  162.                                 ubi_trCompFunc    CompFunc,
  163.                                 ubi_trKillNodeRtn FreeFunc,
  164.                                 unsigned long     MaxEntries,
  165.                                 unsigned long     MaxMemory )
  166.   /* ------------------------------------------------------------------------ **
  167.    * Initialize a cache header structure.
  168.    *
  169.    *  Input:  CachePtr    - A pointer to a ubi_cacheRoot structure that is
  170.    *                        to be initialized.
  171.    *          CompFunc    - A pointer to the function that will be called
  172.    *                        to compare two cache values.  See the module
  173.    *                        comments, above, for more information.
  174.    *          FreeFunc    - A pointer to a function that will be called
  175.    *                        to free a cache entry.  If you allocated
  176.    *                        the cache entry using malloc(), then this
  177.    *                        will likely be free().  If you are allocating
  178.    *                        cache entries from a free list, then this will
  179.    *                        likely be a function that returns memory to the
  180.    *                        free list, etc.
  181.    *          MaxEntries  - The maximum number of entries that will be
  182.    *                        allowed to exist in the cache.  If this limit
  183.    *                        is exceeded, then existing entries will be
  184.    *                        removed from the cache.  A value of zero
  185.    *                        indicates that there is no limit on the number
  186.    *                        of cache entries.  See ubi_cachePut().
  187.    *          MaxMemory   - The maximum amount of memory, in bytes, to be
  188.    *                        allocated to the cache (excluding the cache
  189.    *                        header).  If this is exceeded, existing entries
  190.    *                        in the cache will be removed until enough memory
  191.    *                        has been freed to meet the condition.  See
  192.    *                        ubi_cachePut().
  193.    *
  194.    *  Output: A pointer to the initialized cache (i.e., the same as CachePtr).
  195.    *
  196.    *  Notes:  Both MaxEntries and MaxMemory may be changed after the cache
  197.    *          has been created.  See
  198.    *            ubi_cacheSetMaxEntries() 
  199.    *            ubi_cacheSetMaxMemory()
  200.    *            ubi_cacheGetMaxEntries()
  201.    *            ubi_cacheGetMaxMemory()    (the latter two are macros).
  202.    *
  203.    *        - Memory is allocated in multiples of the word size.  The
  204.    *          return value of the strlen() function does not reflect
  205.    *          this; it will allways be less than or equal to the amount
  206.    *          of memory actually allocated.  Keep this in mind when
  207.    *          choosing a value for MaxMemory.
  208.    *
  209.    * ------------------------------------------------------------------------ **
  210.    */
  211.   {
  212.   if( CachePtr )
  213.     {
  214.     (void)ubi_trInitTree( CachePtr, CompFunc, ubi_trOVERWRITE );
  215.     CachePtr->free_func   = FreeFunc;
  216.     CachePtr->max_entries = MaxEntries;
  217.     CachePtr->max_memory  = MaxMemory;
  218.     CachePtr->mem_used    = 0;
  219.     CachePtr->cache_hits  = 0;
  220.     CachePtr->cache_trys  = 0;
  221.     }
  222.   return( CachePtr );
  223.   } /* ubi_cacheInit */
  224.  
  225. ubi_cacheRootPtr ubi_cacheClear( ubi_cacheRootPtr CachePtr )
  226.   /* ------------------------------------------------------------------------ **
  227.    * Remove and free all entries in an existing cache.
  228.    *
  229.    *  Input:  CachePtr  - A pointer to the cache that is to be cleared.
  230.    *
  231.    *  Output: A pointer to the cache header (i.e., the same as CachePtr).
  232.    *          This function re-initializes the cache header.
  233.    *
  234.    * ------------------------------------------------------------------------ **
  235.    */
  236.   {
  237.   if( CachePtr )
  238.     {
  239.     (void)ubi_trKillTree( CachePtr, CachePtr->free_func );
  240.     CachePtr->mem_used    = 0;
  241.     CachePtr->cache_hits  = 0;
  242.     CachePtr->cache_trys  = 0;
  243.     }
  244.   return( CachePtr );
  245.   } /* ubi_cacheClear */
  246.  
  247. void ubi_cachePut( ubi_cacheRootPtr  CachePtr,
  248.                    unsigned long     EntrySize,
  249.                    ubi_cacheEntryPtr EntryPtr,
  250.                    ubi_trItemPtr     Key )
  251.   /* ------------------------------------------------------------------------ **
  252.    * Add an entry to the cache.
  253.    *
  254.    *  Input:  CachePtr  - A pointer to the cache into which the entry
  255.    *                      will be added.
  256.    *          EntrySize - The size, in bytes, of the memory block indicated
  257.    *                      by EntryPtr.  This will be copied into the
  258.    *                      EntryPtr->entry_size field.
  259.    *          EntryPtr  - A pointer to a memory block that begins with a
  260.    *                      ubi_cacheEntry structure.  The entry structure
  261.    *                      should be followed immediately by the data to be
  262.    *                      cached (even if that is a pointer to yet more data).
  263.    *          Key       - Pointer used to identify the lookup key within the
  264.    *                      Entry.
  265.    *
  266.    *  Output: None.
  267.    *
  268.    *  Notes:  After adding the new node, the cache is "trimmed".  This
  269.    *          removes extra nodes if the tree has exceeded it's memory or
  270.    *          entry count limits.  It is unlikely that the newly added node
  271.    *          will be purged from the cache (assuming a reasonably large
  272.    *          cache), since new nodes in a splay tree (which is what this
  273.    *          module was designed to use) are moved to the top of the tree
  274.    *          and the cache purge process removes nodes from the bottom of
  275.    *          the tree.
  276.    *        - The underlying splay tree is opened in OVERWRITE mode.  If
  277.    *          the input key matches an existing key, the existing entry will
  278.    *          be politely removed from the tree and freed.
  279.    *        - Memory is allocated in multiples of the word size.  The
  280.    *          return value of the strlen() function does not reflect
  281.    *          this; it will allways be less than or equal to the amount
  282.    *          of memory actually allocated.
  283.    *
  284.    * ------------------------------------------------------------------------ **
  285.    */
  286.   {
  287.   ubi_trNodePtr OldNode;
  288.  
  289.   EntryPtr->entry_size = EntrySize;
  290.   CachePtr->mem_used  += EntrySize;
  291.   (void)ubi_trInsert( CachePtr, EntryPtr, Key, &OldNode );
  292.   if( OldNode )
  293.     free_entry( CachePtr, (ubi_cacheEntryPtr)OldNode );
  294.  
  295.   cachetrim( CachePtr );
  296.   } /* ubi_cachePut */
  297.  
  298. ubi_cacheEntryPtr ubi_cacheGet( ubi_cacheRootPtr CachePtr,
  299.                                 ubi_trItemPtr    FindMe )
  300.   /* ------------------------------------------------------------------------ **
  301.    * Attempt to retrieve an entry from the cache.
  302.    *
  303.    *  Input:  CachePtr  - A ponter to the cache that is to be searched.
  304.    *          FindMe    - A ubi_trItemPtr that indicates the key for which
  305.    *                      to search.
  306.    *
  307.    *  Output: A pointer to the cache entry that was found, or NULL if no
  308.    *          matching entry was found.
  309.    *
  310.    *  Notes:  This function also updates the hit ratio counters.
  311.    *          The counters are unsigned short.  If the number of cache tries
  312.    *          reaches 32768, then both the number of tries and the number of
  313.    *          hits are divided by two.  This prevents the counters from
  314.    *          overflowing.  See the comments in ubi_cacheHitRatio() for
  315.    *          additional notes.
  316.    *
  317.    * ------------------------------------------------------------------------ **
  318.    */
  319.   {
  320.   ubi_trNodePtr FoundPtr;
  321.  
  322.   FoundPtr = ubi_trFind( CachePtr, FindMe );
  323.  
  324.   if( FoundPtr )
  325.     CachePtr->cache_hits++;
  326.   CachePtr->cache_trys++;
  327.  
  328.   if( CachePtr->cache_trys & 0x8000 )
  329.     {
  330.     CachePtr->cache_hits = CachePtr->cache_hits / 2;
  331.     CachePtr->cache_trys = CachePtr->cache_trys / 2;
  332.     }
  333.  
  334.   return( (ubi_cacheEntryPtr)FoundPtr );
  335.   } /* ubi_cacheGet */
  336.  
  337. ubi_trBool ubi_cacheDelete( ubi_cacheRootPtr CachePtr, ubi_trItemPtr DeleteMe )
  338.   /* ------------------------------------------------------------------------ **
  339.    * Find and delete the specified cache entry.
  340.    *
  341.    *  Input:  CachePtr  - A pointer to the cache.
  342.    *          DeleteMe  - The key of the entry to be deleted.
  343.    *
  344.    *  Output: TRUE if the entry was found & freed, else FALSE.
  345.    *
  346.    * ------------------------------------------------------------------------ **
  347.    */
  348.   {
  349.   ubi_trNodePtr FoundPtr;
  350.  
  351.   FoundPtr = ubi_trFind( CachePtr, DeleteMe );
  352.   if( FoundPtr )
  353.     {
  354.     (void)ubi_trRemove( CachePtr, FoundPtr );
  355.     free_entry( CachePtr, (ubi_cacheEntryPtr)FoundPtr );
  356.     return( ubi_trTRUE );
  357.     }
  358.   return( ubi_trFALSE );
  359.   } /* ubi_cacheDelete */
  360.  
  361. ubi_trBool ubi_cacheReduce( ubi_cacheRootPtr CachePtr, unsigned long count )
  362.   /* ------------------------------------------------------------------------ **
  363.    * Remove <count> entries from the bottom of the cache.
  364.    *
  365.    *  Input:  CachePtr  - A pointer to the cache which is to be reduced in
  366.    *                      size.
  367.    *          count     - The number of entries to remove.
  368.    *
  369.    *  Output: The function will return TRUE if <count> entries were removed,
  370.    *          else FALSE.  A return value of FALSE should indicate that
  371.    *          there were less than <count> entries in the cache, and that the
  372.    *          cache is now empty.
  373.    *
  374.    *  Notes:  This function forces a reduction in the number of cache entries
  375.    *          without requiring that the MaxMemory or MaxEntries values be
  376.    *          changed.
  377.    *
  378.    * ------------------------------------------------------------------------ **
  379.    */
  380.   {
  381.   ubi_trNodePtr NodePtr;
  382.  
  383.   while( count )
  384.     {
  385.     NodePtr = ubi_trLeafNode( CachePtr->root.root );
  386.     if( NULL == NodePtr )
  387.       return( ubi_trFALSE );
  388.     else
  389.       {
  390.       (void)ubi_trRemove( CachePtr, NodePtr );
  391.       free_entry( CachePtr, (ubi_cacheEntryPtr)NodePtr );
  392.       }
  393.     count--;
  394.     }
  395.   return( ubi_trTRUE );
  396.   } /* ubi_cacheReduce */
  397.  
  398. unsigned long ubi_cacheSetMaxEntries( ubi_cacheRootPtr CachePtr,
  399.                                       unsigned long    NewSize )
  400.   /* ------------------------------------------------------------------------ **
  401.    * Change the maximum number of entries allowed to exist in the cache.
  402.    *
  403.    *  Input:  CachePtr  - A pointer to the cache to be modified.
  404.    *          NewSize   - The new maximum number of cache entries.
  405.    *
  406.    *  Output: The maximum number of entries previously allowed to exist in
  407.    *          the cache.
  408.    *
  409.    *  Notes:  If the new size is less than the old size, this function will
  410.    *          trim the cache (remove excess entries).
  411.    *        - A value of zero indicates an unlimited number of entries.
  412.    *
  413.    * ------------------------------------------------------------------------ **
  414.    */
  415.   {
  416.   unsigned long oldsize = CachePtr->max_entries;      /* Save the old value.  */
  417.  
  418.   CachePtr->max_entries = NewSize;                    /* Apply the new value. */
  419.   if( (NewSize < oldsize) || (NewSize && !oldsize) )  /* If size is smaller,  */
  420.     cachetrim( CachePtr );                            /*   remove excess.     */
  421.   return( oldsize );
  422.   } /* ubi_cacheSetMaxEntries */
  423.  
  424. unsigned long ubi_cacheSetMaxMemory( ubi_cacheRootPtr CachePtr,
  425.                                      unsigned long    NewSize )
  426.   /* ------------------------------------------------------------------------ **
  427.    * Change the maximum amount of memory to be used for storing cache
  428.    * entries.
  429.    *
  430.    *  Input:  CachePtr  - A pointer to the cache to be modified.
  431.    *          NewSize   - The new cache memory size.
  432.    *
  433.    *  Output: The previous maximum memory size.
  434.    *
  435.    *  Notes:  If the new size is less than the old size, this function will
  436.    *          trim the cache (remove excess entries).
  437.    *        - A value of zero indicates that the cache has no memory limit.
  438.    *
  439.    * ------------------------------------------------------------------------ **
  440.    */
  441.   {
  442.   unsigned long oldsize = CachePtr->max_memory;       /* Save the old value.  */
  443.  
  444.   CachePtr->max_memory = NewSize;                     /* Apply the new value. */
  445.   if( (NewSize < oldsize) || (NewSize && !oldsize) )  /* If size is smaller,  */
  446.     cachetrim( CachePtr );                            /*   remove excess.     */
  447.   return( oldsize );
  448.   } /* ubi_cacheSetMaxMemory */
  449.  
  450. int ubi_cacheHitRatio( ubi_cacheRootPtr CachePtr )
  451.   /* ------------------------------------------------------------------------ **
  452.    * Returns a value that is 10,000 times the slightly weighted average hit
  453.    * ratio for the cache.
  454.    *
  455.    *  Input:  CachePtr  - Pointer to the cache to be queried.
  456.    *
  457.    *  Output: An integer that is 10,000 times the number of successful
  458.    *          cache hits divided by the number of cache lookups, or:
  459.    *            (10000 * hits) / trys
  460.    *          You can easily convert this to a float, or do something
  461.    *          like this (where i is the return value of this function):
  462.    *
  463.    *            printf( "Hit rate   : %d.%02d%%\n", (i/100), (i%100) );
  464.    *
  465.    *  Notes:  I say "slightly-weighted", because the numerator and
  466.    *          denominator are both accumulated in locations of type
  467.    *          'unsigned short'.  If the number of cache trys becomes
  468.    *          large enough, both are divided  by two.  (See function
  469.    *          ubi_cacheGet().) 
  470.    *          Dividing both numerator and denominator by two does not
  471.    *          change the ratio (much...it is an integer divide), but it
  472.    *          does mean that subsequent increments to either counter will
  473.    *          have twice as much significance as previous ones.
  474.    *
  475.    *        - The value returned by this function will be in the range
  476.    *          [0..10000] because ( 0 <= cache_hits <= cache_trys ) will
  477.    *          always be true.
  478.    *
  479.    * ------------------------------------------------------------------------ **
  480.    */
  481.   {
  482.   int tmp = 0;
  483.  
  484.   if( CachePtr->cache_trys )
  485.     tmp = (int)( (10000 * (long)(CachePtr->cache_hits) )
  486.                         / (long)(CachePtr->cache_trys) );
  487.   return( tmp );
  488.   } /* ubi_cacheHitRatio */
  489.  
  490. /* -------------------------------------------------------------------------- */
  491.